﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/reverse-linked-list-ii/
/*
题目描述：
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
*/


// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};
 

// 开始解题：
void reverseList(struct ListNode* head, struct ListNode* newhead) {
    struct ListNode* Cur = head;
    struct ListNode* Next = NULL; // 保存cur的下一个节点，以辅助头插
    while (Cur) {
        Next = Cur->next;
        // 头插
        Cur->next = newhead->next;
        newhead->next = Cur;

        // 迭代往后走
        Cur = Next;
    }
}

struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if (NULL == head || NULL == head->next) {
        return head;
    }
    // 先创建一个辅助的哑结点
    struct ListNode* dumbNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    dumbNode->val = -1;
    dumbNode->next = head;
    struct ListNode* cur = dumbNode;
    struct ListNode* leftNode = head;
    struct ListNode* rightNode = NULL;
    struct ListNode* pre = dumbNode; // 记录，leftNode的前一个节点
    struct ListNode* next = NULL; // 记录rightNode的下一个节点
    int len = 0;

    // 先找到各个节点
    while (cur) {
        len++;
        if (len == left) {
            pre = cur;
            leftNode = pre->next;
        }
        if (len == right + 1) {
            rightNode = cur;
            next = rightNode->next;
        }
        cur = cur->next;
    }

    // 断开链表
    pre->next = NULL;
    rightNode->next = NULL;

    // 反转链表
    reverseList(leftNode, pre);

    // 接回原来的链表
    leftNode->next = next;
    return dumbNode->next;
}